#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    static vector<vector<int>> fourSum(vector<int> &nums, int target)
    {
        vector<vector<int>> ret;
        if (nums.size() >= 4)
        {
            //操作思路跟三数之和差不多
            //先固定一个数c，然后要求后面三个数之和等于target-c
            //这里“三数之和”的思路进行解题
            //三数之和
            //固定一个数d，然后用“双指针”的方法求后面两数之和等于target-c-d
            //细节
            //不重
            //不漏
            sort(nums.begin(), nums.end());
            for (int i = 0; i < nums.size() - 3;)
            {
                long long target_i = target - nums[i];
                for (int j = i + 1; j < nums.size() - 2;)
                {
                    int left = j + 1;
                    int right = nums.size() - 1;
                    long long target_j = target_i - nums[j];
                    while (left < right)
                    {
                        long long sum = nums[left] + nums[right];
                        if (sum < target_j)
                            left++;
                        else if (sum > target_j)
                            right--;
                        else
                        {
                            ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});
                            while (left < right && nums[left] == nums[left - 1])
                                left++;
                            while (left < right && nums[right] == nums[right + 1])
                                right--;
                        }
                    }
                    j++;
                    while (nums[j] == nums[j - 1] && j < nums.size() - 2)
                        j++;
                }
                i++;
                while (nums[i] == nums[i - 1] && i < nums.size() - 3)
                    i++;
            }
        }
        return ret;
    }
};

int main()
{
    vector<int> vc = {1, 0, -1, 0, -2, 2};
    auto ans = Solution::fourSum(vc, 0);
    for (auto it : ans)
    {
        for (auto i : it)
        {
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}